/*
day327 
2020.7.20
*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

class Solution1 {
public:
    vector<vector<int>> pairSums(vector<int>& nums, int target) {
		sort(nums.begin(),nums.end());
		vector<vector<int>> res;
		
		int tem=0;
		vector<int> vec_tem(2);
		for(int l=0,r=nums.size()-1;l<r;)
		{
			tem=nums[l]+nums[r];
			if(tem==target)
			{
				vec_tem[0]=nums[l];
				vec_tem[1]=nums[r];
				res.push_back(vec_tem);
			}
			
			if(tem>target)
			{
				r--;
			}
			
			if(tem<target)
			{
				l++;
			}
		}
		
		return res;
    }
};


class Solution {
public:
    vector<vector<int>> pairSums(vector<int>& nums, int target) {
		unordered_map<int,int> m;
		vector<vector<int>> res;
		int count=0; 
		for(int i=0;i<nums.size();++i)
		{
			m[nums[i]]++;
		}
		
		vector<int> vec_tem(2);
		for(auto pair : m)
		{
			count=min(pair.second,m[target-pair.first]);
			
			if(pair.first==target/2)
			{
				count/=2;
			}
			if(count>0)
			{
				m[pair.first]-=count;
				m[target-pair.first]-=count;
				
				vec_tem[0]=pair.first;
				vec_tem[1]=target-pair.first;
				
				for(int i=0;i<count;++i)
				{
					res.push_back(vec_tem);
				}
			}	
		}
		
		return res;
    }
};

int main()
{
	return 0;
 } 
